package dp.medium;


/**
 * 丑数 II
 * 示例 1：
 *
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ugly-number-ii
 */
public class UglyNumberII_264 {
    public int nthUglyNumber(int n) {
        int[] arr = new int[n];
        arr[0] = 1;
        int a2 = 0, a3 = 0, a5 = 0;
        for (int i = 1; i < n; i++) {
            arr[i] = Math.min(Math.min(2  * arr[a2], 3 * arr[a3]), 5 * arr[a5]);
            if (arr[i] == 2  * arr[a2])
                a2++;
            if(arr[i] == 3 * arr[a3])
                a3++;
            if(arr[i] == 5 * arr[a5])
                a5++;
        }
        return arr[n - 1];
    }

    public static void main(String[] args) {
        UglyNumberII_264 ub = new UglyNumberII_264();
        System.out.println(ub.nthUglyNumber(10));
    }
}
